Лемма о немонотонной функции

Пусть $f \notin \mathsf{M}$. Тогда отрицание можно задать формулой над множеством $\{f, 0, 1\}$.

Так как $f$ — немонотонная функция, то существуют наборы $\vec{a}$ и $\vec{b}$, такие что: $$\vec{a} \leqslant \vec{b}, \text{ но } f(\vec{a}) > f(\vec{b}) \implies f(\vec{a}) = 1, f(\vec{b}) = 0$$ Рассмотрим путь от $\vec{a}$ к $\vec{b}$ в $k$-мерном кубе. Так как $\vec{a} \leqslant \vec{b}$, существует цепочка соседних наборов, где каждый следующий покрывает предыдущий. Поскольку значение функции меняется с $1$ на $0$, в этой цепочке найдутся соседние наборы $\vec{\alpha}$ и $\vec{\beta}$, такие что $\vec{\beta}$ покрывает $\vec{\alpha}$ и: $$f(\vec{\alpha}) = 1,~~ f(\vec{\beta}) = 0$$ Наборы $\vec{\alpha}$ и $\vec{\beta}$ отличаются ровно в одном разряде (пусть $i$-ом): $$\vec{\alpha} = (c_1, \dots, 0, \dots, c_k)$$ $$\vec{\beta} = (c_1, \dots, 1, \dots, c_k)$$ Рассмотрим функцию одной переменной, подставив константы $c_j$ на все места, кроме $i$-го: $$\phi(x) = f(c_1, \dots, c_{i-1}, x, c_{i+1}, \dots, c_k)$$ Проверим значения функции: $$\phi(0) = f(\vec{\alpha}) = 1$$ $$\phi(1) = f(\vec{\beta}) = 0$$ Следовательно, $\phi(x) = \bar{x}$. Так как $c_j \in \{0, 1\}$, то $\phi(x)$ является формулой над $\{f, 0, 1\}$. $\square$